{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Scores of Built Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search #string-matching #suffix-array #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找 #字符串匹配 #后缀数组 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumScores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造字符串的总得分和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你需要从空字符串开始&nbsp;<strong>构造</strong> 一个长度为 <code>n</code>&nbsp;的字符串 <code>s</code>&nbsp;，构造的过程为每次给当前字符串 <strong>前面</strong>&nbsp;添加 <strong>一个</strong> 字符。构造过程中得到的所有字符串编号为 <code>1</code>&nbsp;到 <code>n</code>&nbsp;，其中长度为 <code>i</code>&nbsp;的字符串编号为 <code>s<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>s = \"abaca\"</code>&nbsp;，<code>s<sub>1</sub> == \"a\"</code>&nbsp;，<code>s<sub>2</sub> == \"ca\"</code>&nbsp;，<code>s<sub>3</sub> == \"aca\"</code>&nbsp;依次类推。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>s<sub>i</sub></code>&nbsp;的 <strong>得分</strong>&nbsp;为&nbsp;<code>s<sub>i</sub></code> 和&nbsp;<code>s<sub>n</sub></code>&nbsp;的 <strong>最长公共前缀</strong> 的长度（注意&nbsp;<code>s == s<sub>n</sub></code>&nbsp;）。</p>\n",
    "\n",
    "<p>给你最终的字符串&nbsp;<code>s</code>&nbsp;，请你返回每一个<em>&nbsp;</em><code>s<sub>i</sub></code>&nbsp;的&nbsp;<strong>得分之和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"babab\"\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>\n",
    "s<sub>1</sub> == \"b\" ，最长公共前缀是 \"b\" ，得分为 1 。\n",
    "s<sub>2</sub> == \"ab\" ，没有公共前缀，得分为 0 。\n",
    "s<sub>3</sub> == \"bab\" ，最长公共前缀为 \"bab\" ，得分为 3 。\n",
    "s<sub>4</sub> == \"abab\" ，没有公共前缀，得分为 0 。\n",
    "s<sub>5</sub> == \"babab\" ，最长公共前缀为 \"babab\" ，得分为 5 。\n",
    "得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"azbazbzaz\"\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>\n",
    "s<sub>2</sub> == \"az\" ，最长公共前缀为 \"az\" ，得分为 2 。\n",
    "s<sub>6</sub> == \"azbzaz\" ，最长公共前缀为 \"azb\" ，得分为 3 。\n",
    "s<sub>9</sub> == \"azbazbzaz\" ，最长公共前缀为 \"azbazbzaz\" ，得分为 9 。\n",
    "其他 s<sub>i</sub> 得分均为 0 。\n",
    "得分和为 2 + 3 + 9 = 14 ，所以我们返回 14 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-scores-of-built-strings](https://leetcode.cn/problems/sum-of-scores-of-built-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-scores-of-built-strings](https://leetcode.cn/problems/sum-of-scores-of-built-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"babab\"', '\"azbazbzaz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        score=0\n",
    "        for i in range(1,n):\n",
    "            s1 = s[-i:]\n",
    "            if s1 == s[:len(s1)]:\n",
    "                score+=len(s1)\n",
    "            else:\n",
    "                for j in range(len(s1)):\n",
    "                    if s1[j]!=s[j]:\n",
    "                        break\n",
    "                score+=j\n",
    "        score+=n\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        score=0\n",
    "        s1 = ''\n",
    "        for i in range(n-1,0,-1):\n",
    "            s1 = s[i]+s1\n",
    "            if s1 == s[:len(s1)]:\n",
    "                score+=len(s1)\n",
    "            else:\n",
    "                for j in range(len(s1)):\n",
    "                    if s1[j]!=s[j]:\n",
    "                        break\n",
    "                score+=j\n",
    "        score+=n\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "Z 函数（扩展KMP）\n",
    "'''\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        z = self.get_z(s)\n",
    "        z[0] = len(s)\n",
    "        return sum(z)\n",
    "\n",
    "    \n",
    "    def get_z(self, s: str) -> list[int]:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        r = 0\n",
    "        l = 0\n",
    "        for i in range(1, n):\n",
    "            if i > r:\n",
    "                z[i] = 0\n",
    "            else:\n",
    "                z[i] = min(z[i-l], r-i+1)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                z[i] += 1\n",
    "            if i + z[i] - 1 > r:\n",
    "                l = i\n",
    "                r = i + z[i] - 1\n",
    "        return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        def zfun(s):\n",
    "            n = len(s)\n",
    "            z = [0] * n\n",
    "            l, r = 0, 0\n",
    "            for i in range(1, n):\n",
    "                z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "                while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                    l, r = i, i + z[i]\n",
    "                    z[i] += 1\n",
    "            return z\n",
    "        a=zfun(s)\n",
    "        return sum(a)+len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        # use z_function\n",
    "        def z_function(s):\n",
    "            n = len(s)\n",
    "            z = [0] * n\n",
    "            l, r = 0, 0\n",
    "            for i in range(1, n):\n",
    "                if i <= r and z[i - l] < r - i + 1:\n",
    "                    z[i] = z[i - l]\n",
    "                else:\n",
    "                    z[i] = max(0, r - i + 1)\n",
    "                    while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                        z[i] += 1\n",
    "                if i + z[i] - 1 > r:\n",
    "                    l = i\n",
    "                    r = i + z[i] - 1\n",
    "            return z\n",
    "        \n",
    "        return sum(z_function(s))+len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        Z = [0] * n \n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if i < r:\n",
    "                Z[i] = min(Z[i - l], r - i + 1)\n",
    "            while i + Z[i] < n and s[Z[i]] == s[Z[i] + i]:\n",
    "                l, r = i, i + Z[i]\n",
    "                Z[i] += 1 \n",
    "            res += Z[i]\n",
    "        # print(Z)\n",
    "        return res + n\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        z = [0] * n\n",
    "\n",
    "        res, l, r = n, 0, 0\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            z[i] = max(min(z[i - l], r- i + 1), 0)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "\n",
    "                z[i] += 1\n",
    "\n",
    "            res += z[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        z = [0] * n\n",
    "\n",
    "        res, l, r = n, 0, 0\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            z[i] = max(min(z[i - l], r- i + 1), 0)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "\n",
    "                z[i] += 1\n",
    "\n",
    "            res += z[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        l,r,i = 0,-1,0\n",
    "        for i in range(1,n):\n",
    "            if i <= r and (z[i-l] + i - 1 < r or r == n-1):\n",
    "                z[i] = min(z[i-l],n-i)\n",
    "            else:\n",
    "                pos = 0\n",
    "                l,r = i,i-1\n",
    "                while i+pos < n and s[i+pos] == s[pos]:\n",
    "                    z[i] += 1\n",
    "                    pos += 1\n",
    "                    r += 1\n",
    "        return sum(z) + n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        def z_func(s):\n",
    "            n = len(s)\n",
    "            z, l, r = [0] * n, 0, 0\n",
    "            for i in range(1, n):\n",
    "                if i < r:\n",
    "                    z[i] = min(r - i, z[i - l])\n",
    "                while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                    z[i] += 1\n",
    "                if i + z[i] > r:\n",
    "                    l, r = i, i + z[i]\n",
    "            return z\n",
    "        z = z_func(s)\n",
    "        res = sum(z)\n",
    "        return res + len(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        # z-algorithm\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        l, r = 0, 0\n",
    "        for i in range(1, n):\n",
    "            if i <= r and z[i - l] < r - i + 1:\n",
    "                z[i] = z[i - l]\n",
    "            else:\n",
    "                z[i] = max(0, r - i + 1)\n",
    "                while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                    z[i] += 1\n",
    "            if i + z[i] - 1 > r:\n",
    "                l = i\n",
    "                r = i + z[i] - 1\n",
    "        return sum(z) + n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            t = min(z[i - l], r - i + 1)\n",
    "            if t > 0: z[i] = t\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n  # 初始化存储最长公共前缀长度的数组\n",
    "        ans, l, r = n, 0, 0  # ans 是最终答案，l 和 r 是维护最长公共前缀范围的指针\n",
    "\n",
    "        for i in range(1, n):\n",
    "            # 初始假设，根据之前已经找到的最长公共前缀范围来更新 z[i]\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)\n",
    "            \n",
    "            # 通过字符比较来更新 z[i]\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]  # 更新最长公共前缀范围\n",
    "                z[i] += 1  # 增加 z[i] 的值\n",
    "\n",
    "            ans += z[i]  # 将 z[i] 加到最终答案上\n",
    "\n",
    "        return ans  # 返回最终答案\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumScores(self, s: str) -> int:\r\n",
    "        def z_function(s: str) -> List[int]:\r\n",
    "            n = len(s)\r\n",
    "            z = [0] * n\r\n",
    "            l, r = 0, 0\r\n",
    "            for i in range(1, n):\r\n",
    "                if i <= r and z[i - l] < r - i + 1:\r\n",
    "                    z[i] = z[i - l]\r\n",
    "                else:\r\n",
    "                    z[i] = max(0, r - i + 1)\r\n",
    "                    while i + z[i] < n and s[z[i]] == s[i + z[i]]:\r\n",
    "                        z[i] += 1\r\n",
    "                if i + z[i] - 1 > r:\r\n",
    "                    l = i\r\n",
    "                    r = i + z[i] - 1\r\n",
    "            return z\r\n",
    "        # print(z_function(s))\r\n",
    "        return sum(z_function(s)) + len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # z函数（扩展KMP）\n",
    "        z = [0] * n\n",
    "        ans, l ,r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def sumScores(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        z = [0] * n  # 扩展kmp\r\n",
    "        ans, l, r = n, 0, 0\r\n",
    "        for i in range(1, n):\r\n",
    "            # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\r\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  \r\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\r\n",
    "                l, r = i, i + z[i]\r\n",
    "                z[i] += 1\r\n",
    "            ans += z[i]\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "            ans += z[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        \n",
    "        if 1:\n",
    "            n = len(s)\n",
    "            s = '0' + s\n",
    "            ret = n\n",
    "            z = [0] * (n + 1)\n",
    "            l = r = 0\n",
    "            for i in range(2, n + 1):\n",
    "                if i <= r:\n",
    "                    z[i] = min(r - i + 1, z[i - l + 1])\n",
    "                while i + z[i] <= n and s[z[i] + i] == s[z[i] + 1]: z[i] += 1\n",
    "                if i + z[i] > r:\n",
    "                    l, r = i, i + z[i] - 1\n",
    "                ret += z[i]\n",
    "            return ret\n",
    "        # return sum(z_func(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        ans, l, r = n, 0, 0\n",
    "        for i in range(1, n):\n",
    "            z[i] = max(min(z[i - l], r - i + 1), 0)  # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                l, r = i, i + z[i]\n",
    "                z[i] += 1\n",
    "                print('z[i]=', z[i])\n",
    "            ans += z[i]\n",
    "            #print(ans)\n",
    "        #print(z)\n",
    "        return len(z)+sum(z)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        Z = [0] * n \n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if i < r:\n",
    "                Z[i] = min(Z[i - l], r - i + 1)\n",
    "            while i + Z[i] < n and s[Z[i]] == s[Z[i] + i]:\n",
    "                l, r = i, i + Z[i]\n",
    "                Z[i] += 1 \n",
    "            res += Z[i]\n",
    "        # print(Z)\n",
    "        return res + n\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        f = [0 for _ in range(len(s))]\n",
    "        f[0] = len(s)\n",
    "        l = r = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if i > r or f[i - l] >= r - i + 1:\n",
    "                l, r = i, max(i, r)\n",
    "                while r < len(s) and s[r] == s[r - i]:\n",
    "                    r += 1\n",
    "                f[i] = r - i\n",
    "                r -= 1\n",
    "            else:\n",
    "                f[i] = f[i - l]\n",
    "        return sum(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        z = self.get_z(s)\n",
    "        print('z:', z)\n",
    "        z[0] = len(s)\n",
    "        return sum(z)\n",
    "\n",
    "    \n",
    "    def get_z(self, s: str) -> list[int]:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        z[0] = n\n",
    "        l = 0\n",
    "        r = 0\n",
    "\n",
    "        # for i in range(1, n):\n",
    "        #     if i <= r:\n",
    "        #         if z[i-l] <= r - i:\n",
    "        #             z[i] = z[i-l]\n",
    "        #         else:\n",
    "        #             z[i] = r - i\n",
    "        #             # 从i+1继续向后循环匹配\n",
    "        #             while r + 1 + z[i] < n and s[r - l + z[i]] == s[r + 1 + z[i]]:\n",
    "        #                 z[i] += 1\n",
    "        #     else:\n",
    "        #         while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "        #             z[i] += 1\n",
    "\n",
    "        #     if i + z[i] > r:\n",
    "        #         l = i\n",
    "        #         r = i + z[i]\n",
    "\n",
    "        # return z\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if i <= r:\n",
    "                z[i] = min(z[i - l], r - i)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                    z[i] += 1\n",
    "            \n",
    "            if i + z[i] > r:\n",
    "                l = i\n",
    "                r = i + z[i]\n",
    "            \n",
    "        return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "def zAlgo(string: str) -> List[int]:\n",
    "    \"\"\"z算法求字符串每个后缀与原串的最长公共前缀长度\n",
    "\n",
    "    z[0]=0\n",
    "    z[i]是s[i:]与s的最长公共前缀(LCP)的长度 (i>=1)\n",
    "    \"\"\"\n",
    "\n",
    "    n = len(string)\n",
    "    z = [0] * n\n",
    "    left, right = 0, 0\n",
    "    for i in range(1, n):\n",
    "        z[i] = max(min(z[i - left], right - i + 1), 0)\n",
    "        while i + z[i] < n and string[z[i]] == string[i + z[i]]:\n",
    "            left, right = i, i + z[i]\n",
    "            z[i] += 1\n",
    "    return z\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        z=zAlgo(s)\n",
    "        print(z)\n",
    "        return sum(z)+len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        base, mod = 131, 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        h = [0] * (n + 1)\n",
    "        p = [0] * (n + 1)\n",
    "        p[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            h[i] = (h[i - 1] * base + ord(s[i - 1])) % mod\n",
    "            p[i] = p[i - 1] * base % mod\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            l, r = 0, n - i + 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                x = ((h[i - 1 + mid] - h[i - 1] * p[mid]) % mod + mod) % mod\n",
    "                if x == h[mid]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans += r\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        base, mod = 131, 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        h = [0] * (n + 1)\n",
    "        p = [0] * (n + 1)\n",
    "        p[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            h[i] = (h[i - 1] * base + ord(s[i - 1])) % mod\n",
    "            p[i] = p[i - 1] * base % mod\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            l, r = -1, n - i + 2\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                x = ((h[i - 1 + mid] - h[i - 1] * p[mid]) % mod + mod) % mod\n",
    "                if x == h[mid]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            ans += l\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        f = [0]*(n+1)\n",
    "        p = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i] = (f[i-1] * 31 + ord(s[i-1])) % MOD\n",
    "        p[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            p[i] = (p[i-1] * 31 )%MOD\n",
    "        ans = 0\n",
    "        # @cache\n",
    "        def get(l,r):\n",
    "            return f[r+1] - f[l] * p[r-l+1]\n",
    "        def check(l,r):\n",
    "            return get(0,r-l) %MOD == get(l,r)%MOD\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            # 过滤掉二分无法判断一个的情况 + 剪枝\n",
    "            if s[i]!=s[0]:\n",
    "                continue\n",
    "            l = i\n",
    "            r = n-1\n",
    "            while l<r:\n",
    "                mid = l+(r-l+1)//2\n",
    "                if check(i, mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            ans += (l-i+1)\n",
    "            # print(i,ans)\n",
    "        return ans+n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        f = [0]*(n+1)\n",
    "        p = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i] = (f[i-1] * 171 + ord(s[i-1])) % MOD\n",
    "        p[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            p[i] = (p[i-1] * 171 )%MOD\n",
    "        ans = 0\n",
    "        # @cache\n",
    "        def get(l,r):\n",
    "            return f[r+1] - f[l] * p[r-l+1]\n",
    "        def check(l,r):\n",
    "            return get(0,r-l) %MOD == get(l,r)%MOD\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            if s[i]!=s[0]:\n",
    "                continue\n",
    "            l = i\n",
    "            r = n-1\n",
    "            while l<r:\n",
    "                mid = l+(r-l+1)//2\n",
    "                if check(i, mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            ans += (l-i+1)\n",
    "            # print(i,ans)\n",
    "        return ans+n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumScores(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        f = [0]*(n+1)\n",
    "        p = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i] = (f[i-1] * 171 + ord(s[i-1])) % MOD\n",
    "        p[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            p[i] = (p[i-1] * 171 )%MOD\n",
    "        ans = 0\n",
    "\n",
    "        def get(l,r):\n",
    "            return f[r+1] - f[l] * p[r-l+1]\n",
    "        def check(l,r):\n",
    "            return get(0,r-l) %MOD == get(l,r)%MOD\n",
    "        ans = n\n",
    "        for i in range(1,n):\n",
    "            if s[i]!=s[0]:\n",
    "                continue\n",
    "            l = i\n",
    "            r = n-1\n",
    "            while l<r:\n",
    "                mid = l+(r-l+1)//2\n",
    "                if check(i, mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            ans += (l-i+1)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
